from typing import TypeVar,Generic,List
T = TypeVar('T')

class Stack(Generic[T]):
    def __init__(self) -> None:
        self._container: List[T] = []
    
    def push(self,item:T) -> None:
        self._container.append(item)

    def pop(self) -> T:
        return self._container.pop()

    def __repr__(self) -> str:
        return repr(self._container)


num_disk:int = 3
tower_a: Stack[int] = Stack()
tower_b: Stack[int] = Stack()
tower_c: Stack[int] = Stack()

for i in range(1,num_disk+1):
    tower_a.push(i)

####这里面n 的含义  代表挪几个。 这个函数是怎么模拟成   汉诺塔的挪动场景的？
def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n:int) -> None:
    if n==1:
        ###如果只挪一个，那么就直接从begin  到   end
        end.push(begin.pop())
    else:
        ###如果挪动多个。那么  step 1:  先 把 前面  n-1  个 通过   temp 做中转。移动到end.
        hanoi(begin,temp,end,n-1)
        ###step2:把 n 移动到temp  > 因为此时。n-1  个都在 end 上。所以把 第n 个挪动到temp
        hanoi(begin,end,temp,1)
        ###step3:把begin 当作中转，将 temp 上的 n 移动到  end.
        hanoi(temp,end,begin,n-1)


if __name__ == '__main__':
    hanoi(tower_a,tower_c,tower_b,num_disk)
    print(tower_a)
    print(tower_b)
    print(tower_c)
